//1.滑动窗口-串联所有单词的子串
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int n = s.size();
        int len = words[0].size(); //每个字符串的长度(l和r的跨度)
        int m = words.size(); //字符总个数
        unordered_map<string, int> hash1;
        vector<int> ret;
        for(auto x : words) hash1[x]++;
        for(int i = 0; i < len; i++)
        {
            int count = 0; //判断窗口内有效字符串的个数
            int l = i, r = i;
            unordered_map<string, int> hash2; 
            while(r + len - 1 < n)
            {
                string in = s.substr(r, len);
                hash2[in]++; //进窗口
                if(hash2[in] <= hash1[in]) count++;
                if(r + len - l > m * len) //判断窗口合法性
                {
                    string out = s.substr(l, len); 
                    if(hash2[out] <= hash1[out]) count--;
                    hash2[out]--; //出窗口
                    l += len;
                }
                if(count == m) //更新结果
                {
                    ret.push_back(l);
                }
                r += len;
            }
        }
        return ret;
    }
};


//2.滑动窗口 - 最小覆盖子串
//注意, 如果x不存在, 那么hash[x]会自动添加 x-0 的映射关系
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash1; 
        unordered_map<char, int> hash2;
        for(auto x : t) hash1[x]++;
        int kinds = hash1.size();
        int count = 0; // 窗口内有效字符的种类
        int l = 0, r = 0, n = s.size();
        int start = 0, minLen = INT_MAX; // 修正：minLen 初始化为最大值
        
        while(r < n) {
            char in = s[r];
            hash2[in]++; //进窗口
            if(hash2[in] == hash1[in]) count++; //

            while(count == kinds) 
            {
                if(r - l + 1 < minLen)
                {
                    minLen = r - l + 1;
                    start = l;
                }
                
                char out = s[l];
                if(hash2[out] == hash1[out]) count--;
                hash2[out]--;
                l++;
            }
            r++;
        }
        return minLen == INT_MAX ? "" : s.substr(start, minLen);
    }
};